
package com.mindprod.primes;

import java.util.BitSet;

/**
 * calculate primes or a prime near a given number.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.4 2006-03-06
 * @since 1998
 */
final class Primes
{
    // ------------------------------ CONSTANTS ------------------------------

    private static final int FIRST_COPYRIGHT_YEAR = 1998;

    /**
     * not displayed copyright
     */
    private static final String EMBEDDED_COPYRIGHT =
            "Copyright: (c) 1998-2013 Roedy Green, Canadian Mind Products, http://mindprod.com";

    private static final String RELEASE_DATE = "2006-03-06";

    /**
     * embedded version string.
     */
    private static final String VERSION_STRING = "1.4";

    // ------------------------------ FIELDS ------------------------------

    /**
     * true for each odd number if is composite
     */
    private BitSet b;

    /**
     * how many elements max in the seize arra
     */
    private int sieveCapacity;

    // --------------------------- CONSTRUCTORS ---------------------------

    /**
     * constructors
     */
    Primes()
    {
        ensureCapacity( 1000 );
    }

    /**
     * @param capacity - largest number you will be asking if prime. If give too small a number, it will automatically
     *                 grow by recomputing the sieve array.
     */
    private Primes( int capacity )
    {
        ensureCapacity( capacity );
    }

    // -------------------------- OTHER METHODS --------------------------

    /**
     * @param candidate number you want to find a prime near.
     *
     * @return first prime higher than candidate
     */
    int above( int candidate )
    {
        do
        {
            // see what we can find in the existing sieve
            for ( int i = candidate + 1; i <= sieveCapacity; i++ )
            {
                if ( isPrime( i ) )
                {
                    return i;
                }
            }
            // Keep building ever bigger sieves till we succeed.
            // The next prime P' is between P+2 and P^2 - 2.
            // However that is a rather pessimistic upper bound.
            // Ideally some theorem would tell us how big we need to build
            // to find one.
            ensureCapacity( Math.max( candidate * 2, sieveCapacity * 2 ) );
        }// end do
        while ( true );
    }// end above

    /**
     * @param candidate number you want to find a prime near.
     *
     * @return first prime less than candidate
     */
    int below( int candidate )
    {
        for ( candidate--; candidate > 0; candidate-- )
        {
            if ( isPrime( candidate ) )
            {
                return candidate;
            }
        }
        // candidate was 1 or 0 or -ve
        return 0;
    }

    // biggest number we have computed in our sieve.
    // our BitSet array is indexed 0..N (odd only)

    /**
     * Ensure have a sieve to tackle primes as big as n. If we don't allocate a sieve big enough and calculate it.
     *
     * @param n - ensure sieve big enough to evaluate n for primality.
     */
    private void ensureCapacity( int n )
    {
        if ( n > sieveCapacity )
        {
            b = new BitSet( ( n + 1 ) / 2 );
            // starts out all 0, presume all numbers prime
            sieveCapacity = n;
            sieve( n );
        }
        // otherwise existing sieve is fine
    }// end ensureCapacity

    /**
     * calc all primes in the range 1..n, not the first n primes.
     *
     * @param n highest candidate, not necessarily prime.
     *
     * @return list of primes 1..n in an array
     */
    final int[] getPrimes( int n )
    {
        // calculate the primes
        ensureCapacity( n );
        // pass 1: count primes
        int countPrimes = 0;
        for ( int i = 0; i <= n; i++ )
        {
            if ( isPrime( i ) )
            {
                countPrimes++;
            }
        }
        // pass 2: construct array of primes
        int[] primes = new int[ countPrimes ];
        countPrimes = 0;
        for ( int i = 0; i <= n; i++ )
        {
            if ( isPrime( i ) )
            {
                primes[ countPrimes++ ] = i;
            }
        }
        return primes;
    }// end getPrimes

    /**
     * @param candidate - is this a prime?
     *
     * @return true if this number is prime
     */
    boolean isPrime( int candidate )
    {
        ensureCapacity( candidate );
        if ( candidate < 3 )
        {
            return candidate != 0;
        }
        return candidate % 2 != 0 && !b.get( candidate / 2 );
    }

    /**
     * calculate the sieve, bit map of all primes 0..n
     *
     * @param n highest number evalutated by the sieve, not necessarily prime.
     */
    private void sieve( int n )
    {
        // Presume BitSet b set is big enough for our purposes.
        // Presume all even numbers are already marked composite, effectively.
        // Presume all odd numbers are already marked prime (0 in bit map).
        int last = ( int ) ( Math.sqrt( n ) ) + 1;
        for ( int candidate = 3; candidate <= last; candidate += 2 )
        {
            // only look at odd numbers
            if ( !b.get( candidate / 2 )/* if candidate is prime */ )
            {
                // Our candidate is prime.
                // Only bother to mark multiples of primes. Others already done.
                // no need to mark even multiples, already done
                int incr = candidate * 2;
                for ( int multiple = candidate + incr; multiple < n; multiple +=
                        incr )
                {
                    b.set( multiple / 2 );// mark multiple as composite
                }// end for multiple
            }// end if
        }// end for candidate
        // at this point our sieve b is correct, except for 0..2
        // at this point our sieve b is correct, except for 0..2
    }// end sieve
// --------------------------- main() method ---------------------------

    /**
     * Demonstrate and test the methods
     *
     * @param args not used
     */
    public static void main( String[] args )
    {
        System.out.println( "primes under 1,000" );
        Primes calc = new Primes( 1000 );
        int[] primes = calc.getPrimes( 1000 );
        for ( final int prime1 : primes )
        {
            System.out.println( prime1 );
        }
        // demonstrate isPrime, above, below
        System.out.println( "Is 149 prime? " + calc.isPrime( 149 ) );
        System.out.println( "The prime just below 149 is " + calc.below( 149 ) );
        System.out.println( "The prime just above 149 is " + calc.above( 149 ) );
        System.out.println( "Primes just larger than 2^n" );
        calc = new Primes( 10000000 );
        for ( int pow = 8; pow < 10000000; pow *= 2 )
        {
            System.out.println( calc.above( pow ) );
        }
        System.out.println(
                "Validating that isPrime works by comparing it with brute force successive division." );
        for ( int i = 3; i <= 151; i++ )
        {
            boolean prime = true;
            for ( int j = 2; j < i; j++ )
            {
                if ( i % j == 0 )
                {
                    prime = false;
                    break;
                }
            }// end for j
            if ( calc.isPrime( i ) != prime )
            {
                System.out.println( i
                        + " oops: algorithms give different answers" );
            }
        }// end for i
        System.out.println( "done" );
    }// end main
}// end Primes
